package com.yileiqian.util;

public class BinarySearchTree {

	private BSTNode root;

	private BSTNode head;
	private BSTNode temp;

	public BinarySearchTree() {

	}

	public void insert(int key) {
		BSTNode newNode = new BSTNode(key);

		if (root == null) {
			root = newNode;
		} else {
			BSTNode parentNode = root;
			BSTNode currentNode = root;

			while (true) {
				parentNode = currentNode;
				if (parentNode.key > key) {
					currentNode = parentNode.left;
					if (currentNode == null) {
						parentNode.left = newNode;
						return;
					}
				} else if (parentNode.key < key) {
					currentNode = parentNode.right;
					if (currentNode == null) {
						parentNode.right = newNode;
						return;
					}
				}
			}
		}
	}

	public BSTNode search(int key) {
		BSTNode node = root;
		while (node != null) {
			if (node.key == key) {
				return node;
			} else if (node.key > key) {
				node = node.left;
			} else {
				node = node.right;
			}
		}
		return null;
	}

	public BSTNode getMin() {
		BSTNode node = root;
		if (node == null) {
			return null;
		}

		while (node.left != null) {
			node = node.left;
		}
		return node;
	}

	public BSTNode getMax() {
		BSTNode node = root;
		if (node == null) {
			return null;
		}

		while (node.right != null) {
			node = node.right;
		}
		return node;
	}

	public boolean checkBalanced() {
		if (checkBalanced(root) == -1) {
			return false;
		}
		return true;
	}

	private int checkBalanced(BSTNode node) {
		if (node == null) {
			return 0;
		}

		int left = checkBalanced(node.left);
		int right = checkBalanced(node.right);

		if (left < 0 || right < 0) {
			return -1;
		}

		int abs = Math.abs(left - right);
		if (abs > 2) {
			return -1;
		}

		return Math.max(left, right) + 1;
	}

	public BSTNode parent(int key) {
		BSTNode node = root;
		BSTNode parent = null;
		while (node != null) {
			if (node.key == key) {
				return parent;
			} else if (node.key > key) {
				parent = node;
				node = node.left;
			} else {
				parent = node;
				node = node.right;
			}
		}
		return null;
	}

	public BSTNode findPre(int key) {
		Stack<BSTNode> ancesters = new Stack<BSTNode>();

		BSTNode node = root;
		while (node != null) {
			if (node.key == key) {
				break;
			} else {
				ancesters.push(node);
				if (node.key > key) {
					node = node.left;
				} else {
					node = node.right;
				}
			}
		}

		if (node.left == null) {
			BSTNode parent = null;
			while (ancesters.hasNext()) {
				parent = ancesters.pop();
				if (parent.right == node) {
					return parent;
				}
				node = parent;
			}
			return null;
		} else {
			node = node.left;
			while (node.right != null) {
				node = node.right;
			}
			return node;
		}

	}

	public BSTNode findPro(int key) {
		Stack<BSTNode> ancesters = new Stack<BSTNode>();

		BSTNode node = root;
		while (node != null) {
			if (node.key == key) {
				break;
			} else {
				ancesters.push(node);
				if (node.key > key) {
					node = node.left;
				} else {
					node = node.right;
				}
			}
		}

		if (node.right == null) {
			BSTNode parent = null;
			while (ancesters.hasNext()) {
				parent = ancesters.pop();
				if (parent.left == node) {
					return parent;
				}
				node = parent;
			}
			return null;
		} else {
			node = node.right;
			while (node.left != null) {
				node = node.left;
			}
			return node;
		}

	}

	public void delete(int key) {
		BSTNode node = root;
		BSTNode parent = null;

		while (node != null) {
			if (node.key == key) {
				break;
			} else if (node.key > key) {
				parent = node;
				node = node.left;
			} else {
				parent = node;
				node = node.right;
			}
		}

		if (node.left == null && node.right == null) {
			if (parent != null) {
				if (parent.left == node) {
					parent.left = null;
				} else {
					parent.right = null;
				}
			} else {
				root = null;
			}
		} else if (node.left == null || node.right == null) {
			if (parent != null) {
				if (parent.left == node) {
					parent.left = node.left != null ? node.left : node.right;
				} else {
					parent.right = node.left != null ? node.left : node.right;
				}
			} else {
				if (node.left != null) {
					root = node.left;
				} else {
					root = node.right;
				}
			}
		} else {
			BSTNode pro = findPro(key);
			BSTNode proPar = parent(pro.key);

			if (proPar.left == pro) {
				proPar.left = null;
			} else {
				proPar.right = null;
			}

			node.key = pro.key;
		}
	}

	public void accessAll() {
		inOrderTravel(root);
		System.out.println();
	}

	private void inOrderTravel(BSTNode node) {
		if (node != null) {
			inOrderTravel(node.left);
			System.out.print(node.key + " ");
			inOrderTravel(node.right);
		}
	}

	public void treeToDoublyList(BSTNode node) {
		if (node == null) {
			return;
		}
		treeToDoublyList(node.left);

		if (head == null) {
			head = node;
			temp = node;
		} else {
			temp.right = node;
			node.left = temp;
			temp = node;
		}

		treeToDoublyList(node.right);
	}

	public String printTreeByLine() {
		StringBuffer buffer = new StringBuffer();

		Queue<BSTNode> q1 = new Queue<BSTNode>();
		Queue<BSTNode> q2 = new Queue<BSTNode>();

		q1.enqueue(root);

		while (q1.hasNext() || q2.hasNext()) {
			if (q1.hasNext()) {
				BSTNode node = q1.dequeue();

				buffer.append(node.key);
				buffer.append(' ');

				if (node.left != null) {
					q2.enqueue(node.left);
				}
				if (node.right != null) {
					q2.enqueue(node.right);
				}
			} else {
				buffer.append('\n');
				Queue<BSTNode> tq = q1;
				q1 = q2;
				q2 = tq;
			}
		}

		buffer.append('\n');

		System.out.println(buffer.toString());

		return buffer.toString();
	}

	public BSTNode treeToDoublyList() {
		treeToDoublyList(root);
		return head;
	}

	public static void main(String args[]) {

		BinarySearchTree bst = new BinarySearchTree();
		bst.insert(9);
		bst.insert(4);
		bst.insert(6);
		bst.insert(3);
		bst.insert(0);
		bst.insert(2);
		bst.insert(-100);
		bst.insert(10000);
		bst.insert(23);
		bst.insert(5);
		bst.insert(-9999);
		bst.accessAll();

		bst.delete(9);
		bst.delete(-100);
		bst.delete(2);
		bst.delete(4);
		bst.delete(5);
		bst.delete(-9999);
		bst.delete(10000);
		bst.delete(0);
		bst.delete(6);
		bst.delete(3);
		bst.delete(23);
		bst.accessAll();
	}
}

class BSTNode {
	BSTNode left;
	BSTNode right;
	int key;

	public BSTNode(int key) {
		this.key = key;
	}
}
